package algorithm.leetcode.I201to400;

import algorithm.leetcode.ListNode;

public class Q234 {

    public boolean isPalindrome(ListNode head) {
        if (head == null) return false;

        int mid = 0;

        ListNode node = head;
        while (node != null) {
            mid++;
            node = node.next;
        }

        mid >>>= 1;

        node = head;
        for (int i = 0; i < mid; i++) {
            node = node.next;
        }

        ListNode pre = null;
        ListNode post = null;

        while (node != null) {
            post = node.next;
            node.next = pre;
            pre = node;
            node = post;
        }

        while (pre != null && head != null) {
            if (pre.val != head.val) return false;
            pre = pre.next;
            head = head.next;
        }

        return true;

    }

    /**
     * 思路:
     * 先快慢指针让慢指针走到前一半的末尾,同时逆转链表的前一半,直到快指针无法后移
     * 再从逆转的前半和原来次序的后半逐个判断
     * @param head
     * @return
     */
    public boolean isPalindrome2(ListNode head) {
        ListNode fakeHead = new ListNode(-2131);
        fakeHead.next = head;
        ListNode pre = null, post = head, slow = head, fast = fakeHead;
        // boolean isStart = true;

        while (fast.next != null && fast.next.next != null) {
            // 先动快指针,避免前面的逆转影响快指针
            fast = fast.next.next;

            post = slow.next;
            slow.next = pre;
            pre = slow;
            slow = post;
        }

        // 处理奇偶
        if (post.next != null) post = post.next;
        boolean even = true, odd = true;
        while (pre != null) {
            if (post == null) {
                return even && pre.val == slow.val;
            }
            else {
                odd = odd && post.val == pre.val;
                even = even && slow.val == pre.val;
                post = post.next;
                pre = pre.next;
                slow = slow.next;
            }
        }

        return odd;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(2);
        ListNode listNode4 = new ListNode(1);
        // ListNode listNode5 = new ListNode(1);
        listNode1.next = listNode2;
        // listNode2.next = listNode3;
        // listNode3.next = listNode4;
        // listNode4.next = listNode5;

        Q234 q234 = new Q234();
        System.out.println(q234.isPalindrome2(listNode1));
    }
}
